package com.origin.niuke.bit_operation;

/**
 * NC156 数组中只出现一次的数（其它数出现k次）
 * 算法：位运算
 *
 * @author yezh
 * @date 2022/11/18 22:55
 */
public class NC156 {

    public static void main(String[] args) {
        System.out.println(new NC156().foundOnceNumber(new int[]{5, 4, 1, 1, 5, 1, 5}, 3));
    }

    public int foundOnceNumber(int[] arr, int k) {
        // write code here
        int[] cnt = new int[32];
        for (int num : arr)
            for (int j = 0; j < 32; j++) {
                // 因为有负数, 所以要将 num 往右移
//                cnt[j] += (num & (1 << j));
                cnt[j] += (num & 1);
                num >>= 1;
            }
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            ans <<= 1;
            if ((cnt[i] % k) == 1) ans |= 1;
        }
        return ans;
    }

}
